package com.yitiao.data_algorithms.leetcode.editor.cn;

import com.yitiao.data_algorithms.leetcode.editor.cn.base.ListNode;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.TreeNode;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

class RemoveDuplicateLetters {
    // 2022-08-15 17:46:01
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String removeDuplicateLetters(String s) {
            char[] chars = s.toCharArray();
            Map<Character, Integer> count = new HashMap<>();
            // 生成出现次数的map
            for (char c : chars) {
                count.put(c, count.getOrDefault(c, 0) + 1);
            }

            Stack<Character> stack = new Stack<>();
            for (char c : chars) {
                if (!stack.contains(c)) {
                    while (!stack.isEmpty()
                            && count.get(stack.peek()) > 0
                            && c < stack.peek()
                    ) {
                        stack.pop();
                    }
                    stack.push(c);
                }
                count.put(c, count.get(c) - 1);
            }

            StringBuilder sb = new StringBuilder();
            while (!stack.empty()) {
                sb.append(stack.pop());
            }
            // 栈中元素插入顺序是反的，需要 reverse 一下
            return sb.reverse().toString();
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}